//
//  Problem1433.swift
//  TestProject
//
//  Created by 武侠 on 2021/3/26.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1433. 检查一个字符串是否可以打破另一个字符串
 给你两个字符串 s1 和 s2 ，它们长度相等，请你检查是否存在一个 s1  的排列可以打破 s2 的一个排列，或者是否存在一个 s2 的排列可以打破 s1 的一个排列。

 字符串 x 可以打破字符串 y （两者长度都为 n ）需满足对于所有 i（在 0 到 n - 1 之间）都有 x[i] >= y[i]（字典序意义下的顺序）。

 示例 1：
     输入：s1 = "abc", s2 = "xya"
     输出：true
     解释："ayx" 是 s2="xya" 的一个排列，"abc" 是字符串 s1="abc" 的一个排列，且 "ayx" 可以打破 "abc" 。
 示例 2：
     输入：s1 = "abe", s2 = "acd"
     输出：false
     解释：s1="abe" 的所有排列包括："abe"，"aeb"，"bae"，"bea"，"eab" 和 "eba" ，s2="acd" 的所有排列包括："acd"，"adc"，"cad"，"cda"，"dac" 和 "dca"。然而没有任何 s1 的排列可以打破 s2 的排列。也没有 s2 的排列能打破 s1 的排列。
 示例 3：
     输入：s1 = "leetcodee", s2 = "interview"
     输出：true
 */
@objcMembers class Problem1433: NSObject {
    func solution() {
        print(checkIfCanBreak("abc", "xya"))
        print(checkIfCanBreak("abe", "acd"))
        print(checkIfCanBreak("leetcodee", "interview"))
    }
    
    /*
     1: 把s1和s2排序
     2: 然后对比每一个字符,找到第一个 s1[i] > s2[i] 或者 s1[i] < s2[i], 能得到判断的标准是s1打败s2还是s2打败s1
     3: 寻找第一个时，如果s1[i] == s2[i], 继续寻找
     */
    func checkIfCanBreak(_ s1: String, _ s2: String) -> Bool {
        let charts1 = s1.sorted()
        let charts2 = s2.sorted()
        
        var is1 = 0
        for i in 0..<s1.count {
            if is1 == 0 {
                if charts1[i] > charts2[i] {
                    is1 = -1
                } else if charts1[i] < charts2[i] {
                    is1 = 1
                }
                continue
            }
            
            if is1 == -1 {
                if charts1[i] < charts2[i] {
                    return false
                }
            } else {
                if charts2[i] < charts1[i] {
                    return false
                }
            }
        }
        
        return true
    }
}
